`
https://leetcode.cn/problems/longest-increasing-subsequence/
`

/**
 * @param {number[]} nums
 * @return {number}
 */
var lengthOfLIS = function (nums) {
  if (nums.length === 0) return 0
  const tails = [nums[0]]
  for (let i = 1; i < nums.length; i++) {
    const num = nums[i]
    if (num > tails[tails.length - 1]) {
      tails.push(num)
    } else {
      const idx = getFirstGreaterIndex(num)
      tails[idx] = num
    }
  }
  function getFirstGreaterIndex(target) {
    // 线性遍历寻找
    // for (let i = 0; i < tails.length; i++) {
    //     if (tails[i] >= target) {
    //         return i
    //     }
    // }
    // 二分查找
    let left = 0, right = tails.length - 1
    while (left < right) {
      const mid = left + ((right - left) >> 1)
      if (tails[mid] >= target) {
        right = mid
      } else {
        left = mid + 1
      }
    }
    return left
  }

  return tails.length
};